|
In combinatorics, the Dinitz conjecture is a statement about the extension of arrays to partial Latin squares, proposed in 1979 by Jeff Dinitz, and proved in 1994 by Fred Galvin. The Dinitz conjecture, now a theorem, is that given an ''n'' × ''n'' square array, a set of ''m'' symbols with ''m'' ≥ ''n'', and for each cell of the array an ''n''-element set drawn from the pool of ''m'' symbols, it is possible to choose a way of labeling each cell with one of those elements in such a way that no row or column repeats a symbol. The Dinitz conjecture is closely related to graph theory, in which it can be succinctly stated as for natural . It means that the list chromatic index of the complete bipartite graph equals . In fact, Fred Galvin proved the Dinitz conjecture as a special case of his theorem stating that the list chromatic index of any bipartite multigraph is equal to its chromatic index. Moreover, it is also a special case of the edge list coloring conjecture saying that the same holds not only for bipartite graphs, but also for any loopless multigraph. ==References== * * * 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Dinitz conjecture」の詳細全文を読む スポンサード リンク
|